package algorithm;


import java.util.HashMap;
import java.util.Map;

/**
 * @author fangkun
 * @create 2022-05-13-9:16
 *
 * 659
 * 给你输⼊⼀个升序排列的数组 nums（可能包含重复数字），请你判断 nums 是否能够被分割成若⼲个⻓度⾄
 * 少为 3 的⼦序列，每个⼦序列都由连续的整数组成。
 */
public class SplitArrayintoConsecutiveSubsequences {

    public static void main(String[] args) {
        int[] nums = new int[]{1,2,3,4,5};
        boolean possible = isPossible(nums);
        System.out.println(possible);
    }

    public static boolean isPossible(int[] nums) {

        Map<Integer, Integer> countMap = new HashMap<Integer, Integer>();
        Map<Integer, Integer> endMap = new HashMap<Integer, Integer>();
        //初始化nums数量,nums数组为key,value为出现的次数
        for (int x : nums) {
            int count = countMap.getOrDefault(x, 0) + 1;
            countMap.put(x, count);
        }
        //遍历修改两个哈希表
        for (int x : nums) {
            //该nums剩余次数
            int count = countMap.getOrDefault(x, 0);

            if (count > 0) {
                //是否有以x-1结尾的序列
                int prevEndCount = endMap.getOrDefault(x - 1, 0);
                //大于0表示有
                if (prevEndCount > 0) {
                    countMap.put(x, count - 1);
                    endMap.put(x - 1, prevEndCount - 1);
                    endMap.put(x, endMap.getOrDefault(x, 0) + 1);

                } else {
                    //判断当前nums后两个数，没有就不能组成3个一组，所以FALSE
                    int count1 = countMap.getOrDefault(x + 1, 0);
                    int count2 = countMap.getOrDefault(x + 2, 0);

                    if (count1 > 0 && count2 > 0) {
                        //修改哈希表
                        countMap.put(x, count - 1);
                        countMap.put(x + 1, count1 - 1);
                        countMap.put(x + 2, count2 - 1);
                        endMap.put(x + 2, endMap.getOrDefault(x + 2, 0) + 1);
                    } else {
                        return false;
                    }
                }
            }
        }
        return true;
    }

    /*public static boolean isPossible(int[] nums) {

        //key nums数组
        Map<Integer, PriorityQueue<Integer>> map = new HashMap<Integer, PriorityQueue<Integer>>();

        for (int x : nums) {

            if (!map.containsKey(x)) {
                map.put(x, new PriorityQueue<Integer>());
            }
            //如果存在key为x-1
            if (map.containsKey(x - 1)) {

                int prevLength = map.get(x - 1).poll();

                if (map.get(x - 1).isEmpty()) {
                    map.remove(x - 1);
                }
                map.get(x).offer(prevLength + 1);
            } else {
                map.get(x).offer(1);
            }
        }

        Set<Map.Entry<Integer, PriorityQueue<Integer>>> entrySet = map.entrySet();

        for (Map.Entry<Integer, PriorityQueue<Integer>> entry : entrySet) {

            PriorityQueue<Integer> queue = entry.getValue();
            if (queue.peek() < 3) {
                return false;
            }
        }
        return true;
    }*/

}
